package liangtWorkSpace.tree.towtree;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @ClassName TreeQueue
 * @Description : 功能说明
 * @Author : LiangT
 * @Date : 2020/4/15 11:58
 */
public class TreeQueue {
    private int[] array;
    private int size;
    public TreeQueue(){
        array = new int[32];
    }

    /**
     * 入队
     */
    public void enQueue(int key){
        if (size > array.length){
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     * @return
     * @throws Exception
     */
    public int deQueue() throws Exception {
        if (size < 0){
            throw  new Exception("这个队列是空的，不能删除");
        }
        int head = array[0];
        array[0] = array[--size];
        downAdjust();
        return head;
    }

    /**
     * 上浮
     */
    private void upAdjust(){
        int childIndex = size -1;
        int parentIndex = (childIndex -1)/2;
        int tmp = array[childIndex];
        while (childIndex > 0 && tmp > array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = parentIndex/2;
        }
        array[childIndex] = tmp;
    }

    private void downAdjust(){
        int parentIndex = 0;
        int tmp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size){
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]){
                childIndex++;
            }
            if (tmp >= array[childIndex]){
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2*childIndex+1;
        }
        array[parentIndex] = tmp;
    }

    private void resize(){
        int newSize = this.size*2;
        this.array = Arrays.copyOf(this.array,newSize);
    }

    public static void main(String[] args) throws Exception {
        TreeQueue priorityQueue = new TreeQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(9);
        System.out.println("出队元素："+priorityQueue.deQueue());
        System.out.println("出队元素："+priorityQueue.deQueue());
    }
}
